// 188. 买卖股票的最佳时机 IV
// 给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格，和一个整型 k 。
// 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

/**
 * @param {number} k
 * @param {number[]} prices
 * @return {number}
 */
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码已经通过力扣的测试用例，应该可直接成功提交。

var maxProfit = function (max_k, prices) {
  var n = prices.length
  if (n <= 0) {
    return 0
  }
  if (max_k > Math.floor(n / 2)) {
    // 交易次数 k 没有限制的情况
    return maxProfit_k_inf(prices)
  }

  // base case：
  // dp[-1][...][0] = dp[...][0][0] = 0
  // dp[-1][...][1] = dp[...][0][1] = -infinity
  var dp = new Array(n).fill(0).map(() => new Array(max_k + 1).fill(0).map(() => new Array(2).fill(0)))
  // k = 0 时的 base case
  for (var i = 0; i < n; i++) {
    dp[i][0][1] = Number.NEGATIVE_INFINITY
    dp[i][0][0] = 0
  }

  for (var i = 0; i < n; i++)
    for (var k = max_k; k >= 1; k--) {
      if (i - 1 == -1) {
        // 处理 i = -1 时的 base case
        dp[i][k][0] = 0
        dp[i][k][1] = -prices[i]
        continue
      }
      // 状态转移方程
      dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
      dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
    }
  return dp[n - 1][max_k][0]
}

// 第 122 题，k 无限的解法
var maxProfit_k_inf = function (prices) {
  var n = prices.length
  var dp = new Array(n).fill(0).map(() => new Array(2).fill(0))
  for (var i = 0; i < n; i++) {
    if (i - 1 == -1) {
      // base case
      dp[i][0] = 0
      dp[i][1] = -prices[i]
      continue
    }
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i])
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i])
  }
  return dp[n - 1][0]
}
// 详细解析参见：
// https://labuladong.github.io/article/?qno=188


console.log(
  maxProfit(
    2,
    [3, 2, 6, 5, 0, 3]
  )
)

